The application of error correcting codes to data in communication systems ensures reliable processing of communication data and packets to provide high quality of service.
A typical method of error correction is to incorporate parity or similar additional bits in transmitted data bit streams. One standard for achieving error correction is convolutional encoding by a programmable processor, with convolutional encoding being a subset of tree coding techniques. Convolutional encoding utilizes additional coding bits to provide redundancy in transmissions. A number, k, of input binary digits are processed to generate n output binary digits, where n&gt;k. A code rate for such convolutional coding is defined as R=k/n.
In convolutional encoding, a block of n code digits is generated and outputted by the encoder within a particular time unit, with the block of n code digits depending not only on the input block of k digits within the time unit, but also on a block of data digits within a previous span of N time units, in which N&gt;0.
As shown in FIG. 1., a convolutional encoder 10 of the prior art includes an input shift register 12, a logic circuit 14, and an output shift register 16. The convolutional encoder 10 receives k bits in a single input frame 18, which are shifted into the input shift register 12 in each time unit, and concurrently n-bits in the output frame 20 are shifted out by the output shift register 16. Such n bits in the output shift register 16 are generated by the logic circuit 14 from data in the input shift register 12. Thus, every k-bit input frame 18 produces an n-bit output frame 20, with redundancy provided in the output since n&gt;k.
Shift register 12 holds a number K of input frames of k bits plus N previous frames of k bits, so the input shift register 12 is k(K+N) bits in length. The number N is sometimes referred to as the constraint length. The n bits are generated from the stored bits in the input shift register 12 by the logic circuit 14. For example, data from the k(K+N) stages of the input shift register 12 may be added by modulo 2 binary operations to set the bits in the n-stage output register 16.
For a convolutional encoder with a code rate of 1/2 which may be used in the North American Time Division Multiple Access (TDMA) Standard IS-136, the following two generator polynomials may be used in logic circuit 14 to produce the content of register 16: EQU g.sub.0 (D)=1+D.sup.2 +D.sup.4 (1) EQU g.sub.1 (D)=1+D+D.sup.2 +D.sup.3 +D.sup.4 (2)
in which D is a delay operator that may be implemented by a shift operation. For example, g.sub.0 (D) could be obtained by combining the register input with signals tapped at the second and fourth stages of a shift register.
For processing sixteen input bits, the convolutional encoder 10 of FIG. 1 receives the sixteen input bits into a register REG.sub.-- IN serving as the input shift register 12, together with 4 past bits (i.e. N=4), and the register 12 contents are symbolized as: EQU REG.sub.-- IN=b.sub.15,b.sub.14, . . . b.sub.2,b.sub.1,b.sub.0,b.sub.-1, . . . b.sub.-4. (3)
Equations (1)-(2) above may then be implemented in the logic circuit 14, for example, with a pair of registers REG.sub.-- g.sub.0 and REG.sub.-- g.sub.1 in Equations as follows: EQU REG.sub.-- g.sub.0 =REG.sub.-- IN.sym.(REG.sub.-- IN&lt;&lt;2).sym.(REG.sub.-- IN&lt;&lt;4) (4) EQU REG.sub.-- g.sub.1 =REG.sub.-- g.sub.0 .sym.(REG.sub.-- IN&lt;&lt;1) .sym.(REG.sub.-- IN&lt;&lt;3) (5)
with .sym. being an exclusive-OR operation on the registers, and with the "&lt;&lt;S" operation indicating a left shift by S bits, which implements the delays in Equations (1)-(2).
In prior art convolutional encoding, the encoded output is obtained by interleaving REG.sub.-- g.sub.0 and REG.sub.-- g.sub.1 in an output register REG.sub.-- OUT such as the output shift register 16 having thirty-two encoder bits as follows: EQU REG.sub.-- OUT=g.sub.0 [15], g.sub.1 [15], g.sub.0 [14], g.sub.1 [14], . . . g.sub.0 [0], g.sub.1 [0] (6)
in which g.sub.R [I] indicates the I.sup.TH bit of the R.sup.TH register.
Heretofore, such interleaving of registers to obtain the encoded output has required a majority of the processing cycles involved in convolutional encoding procedures. For example, in prior art digital signal processors, 3*m cycles per input bit is a typical processing cycle overhead for a 1/m rate encoder utilizing a Lucent Technologies DSP1600 processor. In contrast, for an encoder utilizing the invention, the processing overhead is three cycles per input bit, regardless of the rate of the encoder.
It is recognized herein that the number of processing cycles for performing convolutional encoding may be reduced by eliminating the interleaving of registers.
In accordance with the present invention a stream of input bits is convolutionally encoded by initially storing a predetermined pattern of bits in an input register together with the input bits. A group of polynomial signals is produced by combining a plurality of variously shifted versions of the input register contents, and the encoded output is generated by combining polynomial signals.